public class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void quickSort(int[] nums, int left, int right){
        if(left < right){
            int p = partition(nums, left, right);

            quickSort(nums, left, p-1);
            quickSort(nums, p+1, right);
        }
    }
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right]; // 选择最右边的元素作为枢轴
        int i = left - 1; // i指向比枢轴小的元素的最后一个位置

        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) { // 注意这里使用了<=，以处理相等的元素
                i++;
                swap(nums, i, j); // 交换元素，使得所有小于等于枢轴的元素都在左边
            }
        }

        swap(nums, i + 1, right); // 将枢轴放置于正确的位置
        return i + 1; // 返回枢轴的位置
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
